//下面这倒题是关于局部有序的二分查找
public class question_33 {
}
class Solution_33 {
//    通过递归的方式进行二分查找，这个数组是局部有序的
    public int re_search(int[] nums,int l,int r,int target){
//        终止条件
        if(l>r){
            return -1;
        }
        int mid=(l+r)/2;
        if(target==nums[l]){
            return l;
        }
        if(target==nums[r]){
            return r;
        }
        if(target==nums[mid]){
            return mid;
        }
//        这里就得利用局部有序的原则了，因为它只进行了一次旋转，比如说[4,5,6,7,0,1,2]，不管mid在哪个位置，都至少有一般是有序的
//        这时就可以利用这个局部的有序数组的头和尾进行排除了
        if(nums[l]<nums[mid]){
            if(target>nums[l]&&target<nums[mid]){
                return re_search(nums,l+1,mid-1,target);
            }else{
                return re_search(nums,mid+1,r-1,target);

            }
        }else{
//            说明是右边部分是有序的
            if(target>nums[mid]&&target<nums[r]){
                return re_search(nums,mid+1,r-1,target);
            }else{
                return re_search(nums,l+1,mid-1,target);
            }
        }


    }
    public int search(int[] nums, int target) {
        int n=nums.length;
        return re_search(nums,0,n-1,target);
    }
}